/**
 *  Copyright (C) 2013  Piotr Szczepański
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package edu.pw.elka.gtsna.community_detection;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

import edu.pw.elka.gtsna.graph.Edge;
import edu.pw.elka.gtsna.graph.Graph;
import edu.pw.elka.gtsna.graph_algorithms.Dijkstra.VerticesComparator;
import edu.pw.elka.gtsna.graph_evaluators.Modularity;
import edu.pw.elka.gtsna.interaction_index.InteractionIndexComputable;

/**
 * @author Piotr Lech Szczepański
 * @author P.Szczepanski@ii.pw.edu.pl 
 *
 */
public class HierarchicalCommunityDetection extends AbstractCommunityDetection {

	InteractionIndexComputable ii;
	
	private Map<Integer, Map<Integer, Double>> iiAmongAll;

	
    CommunityStructure cs;
    CommunityStructure bestCs;
    
    Modularity mod;
    
    double bestModularity;
    double coverage;
    
	public HierarchicalCommunityDetection(Graph graph, InteractionIndexComputable ii){
		super(graph);
		this.ii = ii;
		iiAmongAll = new HashMap<Integer,Map<Integer,Double>>();
		for (int i=0; i< graph.getNumOfNodes(); i++){
			iiAmongAll.put(i, new HashMap<Integer,Double>());
		}
		cs = new CommunityStructure();
		mod = new Modularity(graph);
	}
	
	private void preCompute(){
		for (int n1: graph.getAllNodes()){
			Set<Integer> C = new HashSet<Integer>();
			C.add(n1);
			cs.addCommunity(C);
		}	
		System.out.println("HC precomputing... ");
		for (int c1 : cs.getCommunitiesNumbers()){
			for (int c2 : cs.getCommunitiesNumbers()){
				if (c1 == c2)
					continue;
				int n1 = cs.getCommunity(c1).iterator().next();
				int n2 = cs.getCommunity(c2).iterator().next();
				iiAmongAll.get(c1).put(c2, ii.interaction(n1, n2));
				iiAmongAll.get(c2).put(c1, ii.interaction(n1, n2));
			}
			System.out.print(c1+" ");
		}
		System.out.println(" ");
		
	}
	
	/* (non-Javadoc)
	 * @see edu.pw.elka.gtsna.community_detection.CommunityStructureDetectable#detectCommunities()
	 */
	@Override
	public CommunityStructure detectCommunities() {
		preCompute();
		
		mod.setCommunities(cs);
		bestModularity = mod.evaluate();
		
		System.out.println("Main algorithm... ");
		while (cs.size() != 1) {
			System.out.print(cs.size()+" ");
			int bc1 = -1;
			int bc2 = -1;
			double bII = -graph.getNumOfNodes();
			for (int c1 : cs.getCommunitiesNumbers()) {
				for (int c2 : cs.getCommunitiesNumbers()){		
					if (c1 == c2)
						continue;
					if (iiAmongAll.get(c1).get(c2) > bII) {
						bc1 = c1;
						bc2 = c2;
						bII = iiAmongAll.get(c1).get(c2);
					}
				}
			}
			
			for (int n: cs.getCommunity(bc2)){
				cs.addNode(n, bc1);
			}
			cs.removeCommunity(bc2);
			
			for (int c1 : cs.getCommunitiesNumbers()) {
				if (c1 != bc1){
					iiAmongAll.get(bc1).put(c1, Math.min(iiAmongAll.get(bc1).get(c1), iiAmongAll.get(bc2).get(c1)));
					iiAmongAll.get(c1).put(bc1, Math.min(iiAmongAll.get(bc1).get(c1), iiAmongAll.get(bc2).get(c1)));
				}
			}
			
			mod.setCommunities(cs);
			double modularity = mod.evaluate();
			
			if (bestModularity < modularity){
				bestModularity = modularity;
				bestCs = new CommunityStructure();
				for (int n: graph.getAllNodes()){
					bestCs.addNode(n, cs.getNodeCommunityNumber(n));
				}
			}
			 
		}
		System.out.println(" ");
		
		CommunityStructure bc = new CommunityStructure();
		for (Set<Integer> C: bestCs.getCommunities()) {
			if (!C.isEmpty()) {
				bc.addCommunity(C);
			}
		}
		return bc;
	}

	public double getBestModularity() {
		return bestModularity;
	}

	public void setBestModularity(double bestModularity) {
		this.bestModularity = bestModularity;
	}

	public double getCoverage() {
		return coverage;
	}

	public void setCoverage(double coverage) {
		this.coverage = coverage;
	}

	 
	 
}
